package com.sunny.l62;

public class Solution {

    public static void main(String[] args) {

        String s1 = "xstjzkfpkggnhjzkpfjoguxvkbuopi";
        String s2 = "xbouipkvxugojfpkzjhnggkpfkzjts";

        Solution solution = new Solution();
        System.out.println(solution.isScramble(s1, s2));

    }

    public boolean isScramble(String s1, String s2) {

        if(null == s1 && null == s2){
            return true;
        }else if(null == s1 || null == s2){
            return false;
        }

//        System.out.println(s1+" "+s2);

        if(s1.length() != s2.length()){
            return false;
        }
        if(s1.equals(s2))
            return true;

        int[] rec = new int[26];
        for(int i=0;i<s1.length();i++){
            rec[s1.charAt(i)-'a']++;
            rec[s2.charAt(i)-'a']--;
        }
        for(int i=0;i<26;i++){
            if(rec[i]!=0)
                return false;
        }

        for(int i=1;i<s1.length();i++){
            if(isScramble(s1.substring(0,i),s2.substring(0,i))
                    && isScramble(s1.substring(i),s2.substring(i)))
                return true;
            if(isScramble(s1.substring(0,i), s2.substring(s1.length()-i))
                    && isScramble(s1.substring(i), s2.substring(0,s2.length()-i)))
                return true;
        }

        return false;
    }
}
